import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;


// -------------------------------------------------------------------------
/**
 *  This is a generic implementation of a singly linked list with a head node
 *  and a tail node. We use this to keep track of our free space blocks.
 *  @param <E>
 *
 *  @author Erik Rodriguez and Cory Chase
 *  @version Apr 12, 2013
 */
public class MyLinkedList<E> implements List<E>{

	private Link<E> head;	//Head of the list
	private Link<E> tail;	//Tail of the list
	private Link<E> curr;	//Current link of the list
	private int numLinks;	//Number of list links

	// ----------------------------------------------------------
	/**
	 * Default constructor
	 * @param size
	 */
	public MyLinkedList(int size){
		this();
	}

	// ----------------------------------------------------------
	/**
	 * Specific Constructor
	 */
	public MyLinkedList() {
		curr = tail = head = new Link<E>(null);
		numLinks = 0;
	}

	// ----------------------------------------------------------
	/**
	 * Prepends the data element to the head of the list.
	 * @param e
	 */
	public void prepend(E e){
		Link<E> prevHeadNext = head.next();
		head.setNext(new Link<E>(e, prevHeadNext));
	}

	@Override
	public boolean add(E e) {
		if(numLinks == 0){
			head = new Link<E>(e, null);
			tail = head;
			numLinks++;
		}
		else{
			Link<E> newLink = new Link<E>(e,null);
			tail.setNext(newLink);
			tail = newLink;
			numLinks++;
		}

		return true;
	}

	@Override
	public void add(int index, E element) {
		curr = head;
		for(int i = 0; i != index; i++){
			curr = curr.next();
		}
		Link<E> l = new Link<E>(null);
		l.setData(element);

		Link<E> prevCurrNext = curr.next();
		curr.setNext(l);
		l.setNext(prevCurrNext);
		numLinks++;

	}

	@Override
	public E get(int index) {
		curr = head;
		for(int i = 0; i != index; i++){
			curr = curr.next();
		}
		return curr.getData();
	}

	@Override
	public void clear() {
		head.setNext(null);
		curr = tail = head = new Link<E>(null);
		numLinks = 0;

	}

	@Override
	public boolean isEmpty() {
		if(numLinks == 0){
			return true;
		}
		return false;
	}

	@Override
	public boolean remove(Object o) {
		return false;
	}

	@Override
	public E remove(int index) {
		curr = head;
		Link<E> prevCurr = curr;
		if(index == 0){
			E oldHeadData = head.getData();
			head = head.next();
			numLinks--;
			return oldHeadData;
		}
		else{
			for(int i = 0; i != index; i++){
				prevCurr = curr;
				curr = curr.next();
			}

			E removedData = curr.getData();
			prevCurr.setNext(curr.next());
			numLinks--;
			return removedData;
		}
	}

	@Override
	public E set(int index, E element) {
		curr = head.next();
		for(int i = 0; i != index; i++){
			curr = curr.next();
		}
		E oldData = curr.getData();
		curr.setData(element);
		return oldData;
	}

	@Override
	public int size() {
		return numLinks;
	}




	@Override
	public boolean addAll(Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int indexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public int lastIndexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public ListIterator<E> listIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}



}
